In an on-line coloring, the vertices of a graph are revealed one by one. An algorithm assigns a color to each vertex after it is revealed. When a vertex is revealed, it is also revealed which of the previous vertices it is adjacent to. The on-line chromatic number of a graph, G, is the smallest number of colors an algorithm will need when on-line-coloring G. The algorithm may know G, but not the order in which the vertices are revealed. The problem of determiningif the on-line chromatic number of a graph is less than or equal to k, given a pre-coloring, is shown to be PSPACE-complete.
展开▼
